When words to be transmitted are encoded by an error correcting code, a limited number of erroneous symbols can be corrected. However, if a major part of a word is wrong, then there is no hope of being able to regenerate the word. In order to mitigate this drawback, one known technique consists in interleaving symbols such that the symbols of a given initial code word are spaced apart and a "packet" of errors will only affect one or few of the symbols in each of several different words as observed after deinterleaving.
There are numerous ways in which interleaving may be performed, but the present invention relates more particularly to interleaving generated by a pilot sequence of addresses, as follows:
Symbols are written to and read from a vector of given size. The addresses of the pilot sequence define those locations in a vector from which the next symbol to be transmitted is to be read or to which the following symbol is to be written, which symbol will be transmitted in its turn, when the same address reappears in the pilot sequence.
By way of concrete example, assume that a vector contains six symbols and that it is desired to transmit the following sequence: a b c d e f g h i j k l ... . The pilot sequence is a sequence of sixes. Within each six, each of the six addresses 1, 2, 3, 4, 5, and 6 is selected once, and once only.
Assume that the pilot sequence begins as follows, for example: ##STR1## and assume that the first symbols a to f are already in register embodying said vector.
The register is thus filled as follows: ##STR2##
In this case, the first of the following symbols, i.e., symbol g, takes the second place in the register, and the symbol b previously in that register location is transmitted. The second following symbol (h) replaces the sixth symbol (i.e. f is transmitted and replaced by h). The next symbol (i) takes the first place (a is transmitted and replaced by i). Then the next symbol (j) takes the fifth place (e is transmitted and replaced by j). Then the next symbol (k) takes the fourth place in the register (d is transmitted and replaced by k). And finally the twelfth symbol (l) takes the third place (c is transmitted and replaced by 1).
At this moment, the register contains the seventh through twelfth original symbols in the following order: ##STR3##
The next, i.e. thirteenth, symbol (m) is to be put in the register in the fourth position, since four is the seventh digit in the pilot sequence. Since k is already in this location, k is transmitted and replaced by m.
The fourteenth symbol (n) is to be put in the first position which already contains i: i is therefore transmitted and replaced by n, and so on. The sequence of symbols actually transmitted (i.e. the "channel sequence") when interleaving is performed using the above pilot sequence, finally ends up as follows: ##STR4##
In order to recover the initial train of symbols at the receiving end, it is necessary to perform deinterleaving on the same principles, but by means of an "inverse pilot sequence" derived from the pilot sequence. The inverse pilot sequence is unique, but several methods may be devised for obtaining it.
A simple method of obtaining the inverse pilot sequence from a pilot sequence is the following:
The first n symbols of the above-defined channel sequence are written into a receive vector or register of the same size as that used on transmission. In the above example, n is equal to 6, so the first six symbols of the channel sequence are written into the receive register.
The first element in the inverse pilot sequence is thus the address in this register of the smallest element in the register (where the term "smallest element" is used to mean the symbol having the lowest order number in the sequence of symbols corresponding to the initial encoding prior to interleaving for transmission).
This smallest element is replaced by the following symbol from the channel sequence, and the second element of the inverse pilot sequence is the address of the smallest element in the register after the above change, and so on, ... .
Thus, in order to obtain each element of the inverse pilot sequence, it is necessary to scan the receive register each time in order to find the smallest element. When symbol interleaving is performed, not on registers having six elements only, but on registers of about 10,000 symbols, as is often the case, it then becomes necessary in order to find each series of 10,000 addresses in the inverse pilot sequence to scan through all 10,000 elements of the register 10,000 times and to order them each time in order to find the smallest element, and this suffers from the drawback of being a particularly lengthy procedure.
The invention seeks to remedy this drawback and, by way of example, it makes it possible to divide the time required for calculating the inverse pilot sequence by several thousand.